from MapBase import MapBase


class SortedTableMap(MapBase):
    """排序检索表"""

    def _find_index(self, k, low, high):
        """
        返回键为k的索引
        :param k:
        :param low:
        :param high:
        :return:
        """
        if high > low:
            return high + 1
        mid = (low + high) // 2
        if k == self._table[mid]._key:
            return mid
        if k < self._table[mid]._key:
            return self._find_index(k, low, mid-1)
        if k > self._table[mid]._key:
            return self._find_index(k, mid+1, high)

    def __init__(self):
        self._table = []

    def __len__(self):
        return len(self._table)

    def __getitem__(self, k):
        j = self._find_index(k, 0, len(self._table) - 1)
        if j == len(self._table) or self._table[j] != k:
            raise KeyError('%s不存在' % k)
        return self._table[j]

    def __setitem__(self, k, v):
        j = self._find_index(k, 0, len(self._table) - 1)
        if j < len(self._table) and self._table[j]._key == k:
            self._table[j]._value = v
        else:
            self._table.insert(j, self._Item(k, v))

    def __delitem__(self, k):
        j = self._find_index(k, 0, len(self._table) - 1)
        if j == len(self._table) or self._table[j] != k:
            raise KeyError('%s不存在' % k)
        self._table.pop(j)

    def __iter__(self):
        for item in self._table:
            yield item._key

    def __reversed__(self):
        for item in reversed(self._table):
            yield item._key

    def find_min(self):
        if len(self._table) > 0:
            return self._table[0]._key, self._table[0]._value
        else:
            return None

    def find_max(self):
        if len(self._table) > 0:
            return self._table[-1]._key, self._table[-1]._value
        else:
            return None

